import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        char [] arr=s.toCharArray();
        HashMap<Character,Integer> map=new HashMap<>();
        int len=Integer.MIN_VALUE;
        int j=-1;
        for(int i=0;i<arr.length;i++){
            if(map.containsKey(arr[i])){
                j=Math.max(map.get(arr[i]),j);
                map.put(arr[i],i);
            }else{
                map.put(arr[i],i);
            }
            len=Math.max(len,i-j);
        }
        return len;
    }
    //剑指 Offer 42. 连续子数组的最大和
    public int maxSubArray(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int [] dp=new int[nums.length];
        dp[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=Math.max(nums[i]+dp[i-1],nums[i]);
        }
        int max=Integer.MIN_VALUE;
        for(int i=0;i<dp.length;i++){
            if(max<dp[i]){
                max=dp[i];
            }
        }
        return max;
    }
    //剑指 Offer 40. 最小的k个数
        //top-k问题
        public int[] getLeastNumbers(int[] arr, int k) {
            if(k<=0||arr.length==0||k>arr.length){
                return new int [0];
            }
            //top-k问题
            PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
            for(int i=0;i<arr.length;i++){
                if(i<k){
                    queue.offer(arr[i]);
                }else{
                    //比较堆首元素和当前元素的大小
                    //小，堆首元素出堆，该元素入堆
                    if(arr[i]<queue.peek()){
                        queue.poll();
                        queue.offer(arr[i]);
                    }
                }
            }
            int [] tmp=new int[k];
            int i=0;
            while(!queue.isEmpty()){
                tmp[i++]=queue.poll();
            }
            return tmp;
        }
    //数组元素的个数超过数组长度的一半
    public int majorityElement(int[] nums) {
        PriorityQueue<Integer>queue=new PriorityQueue<>();
        queue.isEmpty();
        int a=0;
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                int val=map.get(nums[i]);
                val=val+1;
                if(val>nums.length/2){
                    a=nums[i];
                    break;
                }
                map.put(nums[i],val);
            }else{
                map.put(nums[i],1);
            }
        }
        return a;
    }
    //复杂链表的复制
    class Node{
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map=new HashMap<>();
        Node cur=head;
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    //根节点到叶子节点满足目标值
    LinkedList<List<Integer>> arr=new LinkedList<>();
    LinkedList<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> pathSum1(TreeNode root, int target) {
           dfs(root,target);
           return arr;
    }
    public void dfs(TreeNode root,int target){
       if(root==null){
           return;
       }
       tmp.add(root.val);
       target=target-root.val;
       if(target==0&&root.left==null&&root.right==null){
           arr.add(new LinkedList(tmp));
       }
       dfs(root.left,target);
       dfs(root.right,target);
       tmp.removeLast();
        HashMap<Integer,Integer>map=new HashMap<>();
    }
}